Discrete Fourier transformed, DFT, can be used to analyze the frequency components of an analog wave. The wave is sampled at a rate f.sub.s until N samples have been obtained and computations are made in accordance with the equation below so as to derive the amplitude of each of N frequencies. The highest position frequency is f.sub.s /2, and the frequencies are separated from each other by f.sub.s /N. In the equation, k is the frequency indice and n is the time indice. ##EQU1## By substituting (2) into (1) we obtain ##EQU2## The total number of computations required for a complete analysis is proportional to N.sup.2 so as to become execessive for reasonable values of N.
By using a Fast Fourier Transform, FFT, the number of computations required to derive from N input samples the amplitudes of N frequency components is reduced from N.sup.2 calculations to NlogN calculations. This is accomplished by noting that all values of the factor W.sub.N.sup.kn are not unique. If k equals 1 in equation (3), it can be seen that as n varies from 0 to N, the factor e.sup.-j[(2.pi./N)kn] is a vector of unit length that rotates through 360.degree. in discrete steps of 2.pi./N; and if k equals 2, the vector rotates through two revolutions in discrete steps of 4.pi./N. Thus, as the values of k increase so do the number of revolutions and the angular size of the steps. Therefore, for any value of k, all the vector positions correspond to a position of the vector when k equaled one so that these values can be used over and over again instead of being computed each time.
There is a myriad of ways in which an FFT can perform the required computations, but in general what is known as a "butterfly" operation is performed on each of different groups of a given number of successive samples. When all of the samples have been subjected to a butterfly operation, a first pass has been completed. If there are N samples, there will be N outputs of all the butterfly operations of the pass. Butterfly operations are then performed on different groups of the same given number of butterfly outputs. When all the outputs have been subjected to a butterfly operation, a second pass is completed. If the given number of samples or outputs subjected to each butterfly operation is n, then the number of passes P is determined by the expression n.sup.P =N. The number n is known as the radix for the FFT. By way of example, if n=2 and N=8, three passes will be required. The number of butterfly operations in each pass is N/n so that, in this example, each pass would have four butterfly operations.
Each butterfly operation contains at least one adder so that if the amplitude of the wave being analyzed is too large, some of the adders can overflow due to finite word-sized limits carried in hardware and thereby produce incorrect amplitudes for the N frequencies. The butterfly operation also includes multiplying means but the multiplication operation presents no overflow because the .vertline.W.sub.N .vertline. multiplicand is always equal to or less than unity.
FFTs can be used in both continuous and pulsed Doppler apparatus for the purpose of analyzing the frequencies represented by the Doppler signals. In a pulsed Doppler system, pulses of a few cycles of carrier frequency w.sub.c are transmitted by a transducer into a region containing the structures for which the velocities are to be determined. Because each structure may have a different velocity, the frequency of the reflections from the various structures may differ from w.sub.c by an amount depending on the absolute value of the velocity. The envelope of the reflected wave after N pulses is the analog wave to be examined. It is sampled at the Nyquist rate with respect to the highest frequency above w.sub.c that is of interest. If only absolute values of frequency are to be determined, the samples are uniformly spaced and are called "real" samples; but if the direction of each velocity is to be determined as well, each real sample is followed by an imaginary sample that is spaced from it by the duration of one-quarter of a cycle of w.sub.c.